#include <iostream>

using namespace std;

struct ListNode
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) { }
    ListNode(int x) : val(x), next(nullptr) { }
    ListNode(int x, ListNode *next) : val(x), next(next) { }
};

class Solution
{
public:
    ListNode* mergeTwoLists_1(ListNode *list1, ListNode *list2)
    {
        if (list1 == nullptr) {
            return list2;
        } else if (list2 == nullptr) {
            return list1;
        } else if (list1->val < list2->val) {
            list1->next = mergeTwoLists_1(list1->next, list2);
            return list1;
        } else if (list2->val < list1->val) {
            list2->next = mergeTwoLists_1(list1, list2->next);
            return list2;
        }
    }

    ListNode* mergeTwoLists_2(ListNode *list1, ListNode *list2)
    {
        ListNode *preHead = new ListNode(-1);  // 哨兵节点
        ListNode *prev = preHead;
        while (list1 != nullptr && list2 != nullptr) {
            if (list1->val < list2->val) {
                prev->next = list1;
                list1 = list1->next;
            } else {
                prev->next = list2;
                list2 = list2->next;
            }
            prev = prev->next;
        }
        // 合并后 list1 和 list2 最多只有一个还未被合并完,
        // 我们直接将链表末尾指向未合并完的链表即可
        prev->next = (list1 == nullptr ? list2 : list1);
        return preHead->next;
    }
};

int main()
{
    cout << "Hello World!" << endl;
    return 0;
}
